GRAMÁTICAS
FORMALES Y
EXPRESIONES
REGULARES

“En esencia, la gramática es una y la misma en todas las lenguas, si bien varía accidentalmente” (Roger Bacon)

“La totalidad de las proposiciones es el lenguaje” (Wittgenstein, Tractatus 4.001)

“Entender un lenguaje significa dominar una técnica” (Wittgenstein, Investigaciones Filosóficas)


Gramáticas Formales

Una gramática formal es un conjunto de reglas de producción que especifican las posibles cadenas de caracteres que definen un lenguaje formal. Evidentemente, una gramática formal solo describe las formas de las cadenas de caracteres, pues un lenguaje no puede expresar su propia semántica.

Las reglas de producción son de la forma P → Q o bien P ::= Q, siendo P y Q (los lados izquierdo y derecho, respectivamente, de la regla), en general, cadenas de caracteres (símbolos terminales) y símbolos no terminales. Ejemplos:
  1. S → bS   S → c
    representan el lenguaje {c, bc, bbc, bbbc, bbbbc, ...}.

  2. S → aBc   B → u   B → uB
    representan el lenguaje {auc, auuc, auuuc, auuuuc, ...}.
Características de las reglas: Una gramática se puede considerar el “generador” de todas las posibles cadenas de caracteres del lenguaje. Una gramática también puede utilizarse para “reconocer” si una determinada cadena de caracteres pertenece o no a un lenguaje determinado. Son dos procesos contrarios: uno hacia adelante y otro hacia atrás.

El lenguaje de las gramáticas (las reglas de producción) es realmente un metalenguaje que permite describir lenguajes particulares.


La jerarquía de Chomsky

El concepto de gramática generativa fue introducido por Noam Chomsky en 1956. Por su carácter abstracto, formalizó la lingüística.

La llamada “jerarquía de Chomsky” es una clasificación de los lenguajes formales basada en los distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía consta de 4 niveles, de mayor a menor generalidad, y en donde cada nivel engloba a los inferiores:
  1. Gramáticas de tipo 0 (sin restricciones). Incluyen a todos las gramáticas formales.

  2. Gramáticas de tipo 1 (gramáticas sensibles al contexto), que generan los lenguajes sensibles al contexto. Las reglas son de la forma αAβ → αγβ, siendo A no terminal y α. β y γ cadenas de símbolos terminales y no terminales. Las cadenas α y β pueden ser vacías (∧).

  3. Gramáticas de tipo 2 (gramáticas libres del contexto), que generan los lenguajes independientes del contexto. Las reglas son de la forma A → γ, siendo A no terminal y γ una cadena de terminales y no terminales.

  4. Gramáticas de tipo 3 (gramáticas regulares), que generan los lenguajes regulares. Las reglas de producción son de la forma A → a, A → ∧ y A → aB o A → aB, siendo a un símbolo terminal, y A y B símbolos no terminales.

Expresiones Regulares

Las expresiones regulares, estudiadas por primera vez por Stephen Kleene [1956], sirven para describir lenguajes. Un lenguaje es un conjunto de cadenas de símbolos de un cierto alfabeto Σ. El lenguaje asociado a una expresión regular r se denota por L(r) y el conjunto correspondiente se denomina “conjunto regular”.

Dos expresiones regulares r y s se dice que son equivalentes si L(r) = L(s).

Las reglas que definen las expresiones regulares sobre un alfabeto Σ son de dos tipos: reglas iniciales y reglas combinatorias.


Reglas iniciales
  1. (cadena vacía) es una expresión regular que representa al conjunto {∧}.

  2. Si a es un símbolo de Σ, a es una expresión regular que representa al conjunto {a}.

  3. Si r es una expresión regular que designa a L(r), entonces (r) es otra expresión regular que está incluido en L(r).

Reglas combinatorias

Las expresiones regulares se forman mediante los mecanismos combinatorios siguientes: Alternativa, Repetición y Concatenación, junto con un mecanismo de Distribución asociado a Alternativa.
  1. Alternativa.
    Se usa el símbolo “|”.

    Si r y s son expresiones regulares, entonces r|s es otra expresión regular que representa a la unión de L(r) y L(s): L(r) ∪ L(s).

    Ejemplos:

    r = a|b|c   L(r) = {a, b, c}
    s = a|b|d   L(s) = {a, b, d}
    r|s = a|b|c|d   L(r|s) = L(r) ∪ L(s) = {a, b, c, d}

  2. Repetición.
    Se utiliza el símbolo "*" (como superíndice) para indicar cero o más repeticiones de la expresión regular concatenada. Cero repeticiones es la cadena vacía.

    Si r es una expresión regular, r* es la expresión regular


    La repetición es un caso particular de alternativa, en este caso para describir alternativas de longitud infinita.

    Ejemplos:


  3. Concatenación.
    No hay operador explícito. Si r y s son expresiones regulares. entonces rs es otra expresión regular. Por ejemplo, si a, b y c son símbolos de Σ, entonces abc es la cadena formada por la concatenación de los símbolos a, b y c.

    La operación de concatenación es distributiva respecto a la alternativa (expresada ésta de forma explícita mediante el operador “|” o de forma implícita mediante el operador “*”).

    Ejemplos:


Prioridad de los operadores

Con el objeto de ahorrar paréntesis se utilizan los convenios siguientes:
  1. Las prioridades, de mayor a menor, son: “*”, concatenación y “|”.
  2. Las tres operaciones son asociativas por la derecha.
Por ejemplo, a|b*c se interpreta como a|((b*)c), es decir, el conjunto de cadenas formadas bien por a, o por cero o más b's seguidas de c:
Propiedades

PropiedadExpresiones
Conmutativar|s = s|r
Asociativa(rs)t = r(st)
(r|s)|t = r|(s|t)
Distributivar(s|t) = rs|rt
(r|s)t = rt|st
Idempotenciar** = r*
Repetición de Alterativa(a|b)* = (a*b*)*
Cadena vacíar∧ = ∧r = r
∧* = ∧
(r|∧)* = r*
Elementos igualesr|r = r


Ampliación de la notación

Con el objeto de simplificar la especificación de ciertas construcciones que aparecen con mucha frecuencia se utilizan los símbolos siguientes:
  1. + (signo “+” como superíndice): indica repetición de una o más veces:


    Se cumple que


  2. Exponentes. Sirven para indicar repetición de una expresión regular un número finito de veces:


  3. ?: indica aparición opcional.

    r? es una abreviatura de r|∧. Por lo tanto, L(r?) = L(r)∪{∧}

  4. -: indica rango, junto con corchetes.


    Por extensión, [abc] equivale a a|b|c

    Ejemplos:


Expresión regular y gramática

Todo lenguaje que se pueda describir mediante una expresión regular también se puede describir mediante una gramática regular. Por ejemplo, la expresión regular a*b* se puede expresar mediante la gramática regular
Limitaciones de las expresiones regulares

A efectos de descripción de un lenguaje, las expresiones regulares tienen la ventaja de proporcionar una notación más compacta y comprensible que una gramática regular. Pero tienen limitaciones:
Definiciones regulares

Con el objeto de superar esta última limitación, se utilizan las llamadas “definiciones regulares”: se dan nombres a expresiones regulares, utilizando la misma sintaxis que las reglas de una gramática, utilizándose dichos nombres como si fueran símbolos.

Para distinguir los símbolos de los nombres, se suelen escribir estos últimos en negrita. Por ejemplo, los identificadores de Pascal se definen así:
Especificación en MENTAL de Gramáticas Formales y Expresiones Regulares

Gramáticas formales

Una regla de producción se especifica mediante una expresión de sustitución diferida, que indica representación. Por ejemplo, las reglas que representan el lenguaje {auc, auuc, auuuc, auuuuc, ...}, se expresan como una gramática (g):
Expresiones regulares
Ventajas de MENTAL para representar lenguajes

Bibliografía